package org.example.myleet.p464;

/**
 * 参考宫水三叶：https://leetcode.cn/problems/can-i-win/solution/by-ac_oier-0ed9/
 */
public class Solution {

    private int maxChoosableInteger;
    private int desireTotal;
    private int[][] dp;

    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        //讨论两种特殊情况
        if ((double)(1 + maxChoosableInteger) * ((double)maxChoosableInteger / 2.0) < desiredTotal) {
            //取完所有数字都不能到达desiredTotal
            return false;
        }
        if (maxChoosableInteger >= desiredTotal) {
            //先手一选就能赢
            return true;
        }
        this.maxChoosableInteger = maxChoosableInteger;
        this.desireTotal = desiredTotal;
        dp = new int[1 << 20][2];
        dfs(0, 0, 0);
        return dp[0][0] == 1;
    }

    private int dfs(int state, int total, int k) {
        if (dp[state][k % 2] != 0) {
            //已经在记忆中搜索过，无需再次搜索
            return dp[state][k % 2];
        }
        //side - 第k轮时，轮到p1（0）还是p2（1）
        int side = k % 2;
        //hope - 第k轮时，如果出现获胜方，算玩家p1赢（1）还是p1输（-1，也即p2赢）
        int hope = k % 2 == 0 ? 1 : -1;
        for (int i = 1; i <= maxChoosableInteger; ++i) {
            //idx - 选第i位数字的位置
            int idx = 1 << (i - 1);
            if ((state & idx) == 0) {
                //第i位数字未选而可选
                if (total + i >= desireTotal) {
                    //当前state可以在此步中选取第i位数字而获胜，记录本方胜利
                    dp[state][side] = hope;
                    return dp[state][side];
                }
                //未达到其中一方胜利状态，选取当前数字i，进入下一个状态
                int nState = state | idx;
                int nextRoundResult = dfs(nState, total + i, k + 1);
                if (nextRoundResult == hope) {
                    //下一步选取结果是与本步的胜利结果相同，则本步的玩家获胜
                    dp[state][side] = hope;
                    return dp[state][side];
                }
            }
        }
        //所有数字都已经选取过，且本步玩家不能获胜，记本步玩家输
        dp[state][side] = -hope;
        return dp[state][side];
    }
}
